package com.base.binarytree;

/**
 * 563. 二叉树的坡度
 *给定一个二叉树，计算 整个树 的坡度 。
 *
 * 一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
 *
 * 整个树 的坡度就是其所有节点的坡度之和
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-tilt
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author leon
 * @date 2021年11月18日 14:09
 */
public class FindTilt {
    int res = 0;
    /**
     * 一重递归,要避免双重或者多重递归
     * 在递归的过程中既要，求树的和，又要，求左右子树的差，将差值我们可以保存的预设的对象属性里面。
     * @param root
     * @return
     */
    public int findTilt(TreeNode root){
        dfs(root);
        return res;
    }

    public int dfs(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftSum = dfs(root.left);
        int rightSum = dfs(root.right);
        //求差
        res+=Math.abs(leftSum-rightSum);
        //求和
        return leftSum+rightSum+root.val;
    }
}
